#include <cstdio>

int check( long long a, long long p )
{
    int i, pos = 1, n = ( p - 1 ) / 2;
    long long ret = 1;
    if ( a % p == 0 )
        return 0;
    while ( pos <= n ) pos <<= 1;
    while ( pos )
    {
        ret = ret * ret % p;
        if ( pos & n )
            ret = ret * a % p;
        pos >>= 1;
    }
    if ( ret == 1 )
        return 1;
    if ( ret == p - 1 )
        return -1;
    return 0;
}

int main( )
{
    long long a, n;
    long long i;
    int ans;
    while ( scanf("%I64d%I64d", &a, &n) != EOF )
    {
        i = 2;
        ans = 1;
        while ( i * i <= n )
        {
            while ( n % i == 0 )
            {
                n /= i;
                ans *= check( a, i );
            }
            i++;
        }
        if ( n > 1 )
            ans *= check( a, n );
        printf("%d\n", ans);
    }
    return 0;
}
